// https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    public String serialize(TreeNode root) {
        // write your code here
        StringBuilder sb = new StringBuilder();
        List<TreeNode> list = new ArrayList<>();
        if (root == null) {
            return "";
        }
        list.add(root);
        while (list.size() > 0) {
            List<TreeNode> new_list = new ArrayList<>();
            for (TreeNode node : list) {
                if (sb.length() > 0) {
                    sb.append(',');
                }
                if (node != null) {
                    sb.append(node.val);
                } else {
                    sb.append('#');
                }
                if (node != null) {
                    new_list.add(node.left);
                    new_list.add(node.right);
                }
            }
            list = new_list;
        }
        int end = sb.length() - 1;
        while (end > 0) {
            if (sb.charAt(end) == '#') {
                end -= 2; // 要处理',''
            } else {
                break;
            }
        }
        return sb.substring(0, end + 1);
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    public TreeNode deserialize(String data) {
        // write your code here
        if (data.length() == 0) {
            return null;
        }
        String[] parts = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(parts[0]));
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        int i = 1;
        while (i < parts.length) {
            List<TreeNode> new_list = new ArrayList<>();
            for (TreeNode node : list) {
                if (!parts[i].equals("#")) {
                    node.left = new TreeNode(Integer.valueOf(parts[i]));
                }
                if (node.left != null) {
                    new_list.add(node.left);
                }
                ++i;
                if (i < parts.length) {
                    if (!parts[i].equals("#")) {
                        node.right = new TreeNode(Integer.valueOf(parts[i]));
                    }
                    if (node.right != null) {
                        new_list.add(node.right);
                    }
                    ++i;
                }
            }
            list = new_list;
        }
        return root;
    }
}